package 链表.k个一组反转链表;
/**
 * 题目描述：
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，
 * 那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 * 输入：head = [1,2,3,4,5], k = 3
 * 输出：[3,2,1,4,5]
 * 力扣地址：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 * 力扣题：25
 * 复杂度
 * 时间复杂度：O(n * k)
 * 空间复杂度：O(1)
 * */
/**
 * 解题思路：
 * 链表可以分区为已反转部分+待翻转部分+未翻转部分
 * 每次翻转前要确定翻转链表的范围，这个必须通过k此循环来确定
 * 需要记录翻转链表的前驱和后继，方便翻转完成后吧已翻转部分和未翻转部分连接起来
 * 初始需要两个变量pre和end，pre代表翻转链表的前驱，end代表翻转链表的末尾
 * 经过k循环，end到达末尾，记录待翻转链表的后继next=end.next
 * 翻转链表，然后将三部分连接起来，然后重置pre和end指针，然后进入下一个循环
 * 当翻转部分长度不足k时，在定位end完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可
 * */

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 记录带反转的前驱节点-
        ListNode pre = dummy;
        // 用于定位带反转的最后一个节点
        ListNode end = dummy;
        while(end.next != null){
            // 移动end指针找到当前的第k个节点（尾节点）
            for(int i = 0;i < k && end != null; i++){
                end = end.next;
            }
            // 如果剩余节点不足k个跳出循环
            if(end == null){
                break;
            }
            // 当前组的第一个头节点
            ListNode start = pre.next;
            // 下一组的第一个头节点a
            ListNode next = end.next;
            // 切断与下一组的链接，方便反转
            end.next = null;
            // 反转当前组
            pre.next = reverse(start);
            // 反转后，原头节点（先尾节点）
            start.next = next;
            pre = start;
            end = pre;
        }
        return dummy.next;
    }
    private ListNode reverse(ListNode head){
        // 前驱节点
        ListNode pre = null;
        // 当前节点
        ListNode curr = head;
        while(curr != null){
            // 暂存下一个指针
            ListNode next = curr.next;
            // 当前指针指向前驱
            curr.next = pre;
            // 前驱后移
            pre = curr;
            // 指针后移
            curr = next;
        }
        return pre;
    }
}

